package org.xqh.study.leetcode.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName SingleNumber
 * @Description 从数组中 查找 只出现一次的数字
 * @Author xuqianghui
 * @Date 2020/12/28 9:56
 * @Version 1.0
 */
public class SingleNumber {

    public static void main(String[] args) {
        int a = 10;
        a &= -a;
        System.out.println(a);
        System.out.println(Integer.toBinaryString(-10));
//        HashMap map = new HashMap();
//        map.getOrDefault()
        /**
         * 10 1010  -10  =  0101 +1 = 0110 & 1010 = 0010 = 2
         * -10 = 10110 -1 = 1 0101 取反 11010
         */
//        int[] nums = {1, 2, 1, 2, 1, 3, 2};
//        System.out.println(JSON.toJSONString(singleNumber4(nums)));
//        System.out.println(singleNumber2(nums));
//        System.out.println(Integer.toBinaryString(-10));
//        System.out.println(Integer.parseInt("111", 2));

//        int[] arr = new int[1];
//        System.out.println(Integer.toBinaryString(1211222333));
//        System.out.println(arr[0]);
        /**
         * // -3补码: 1 1101                 0011 --> 1100 + 1= 1101
         *    5补码:  0 0101
         *    ==        0101 == 5
         */
//        System.out.println(5 & -2);
//
//        /**
//
//         */
//        System.out.println(-3 & -5);
    }

    public static int singleNumber(int[] nums){
        int[] tmp = new int[32];
        for(int n:nums){
            String binary = Integer.toBinaryString(n);
            char[] chars = binary.toCharArray();
            for(int i = 0; i < chars.length; i++){
                tmp[31 - i] += (chars[chars.length - 1 - i] - '0');
            }
        }
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < tmp.length; i ++){
            tmp[i] = tmp[i]%3;
            sb.append(tmp[i]);
        }

        return Integer.parseUnsignedInt(sb.toString(), 2);
    }

    public static int singleNumber3(int[] nums){
        int res = 0;
        for(int i = 0; i<32; i++){
           int count = 0;
           for(int j = 0; j < nums.length; j++){
               //先将数右移, 并求出最后一位为1 的个数
               if((nums[j] >> i & 1) == 1){
                   count ++;
               }
           }
            //找到某一位取余为 1 的数，并左移，为了将这一位循环结束后移至原位
            if (count % 3 != 0) {
                res = res | (1 << i);
            }
        }
        return res;
    }

    public static int singleNumber2(int[] nums) {
        int seenOnce = 0, seenTwice = 0;

        for (int num : nums) {
            // first appearance:
            // add num to seen_once
            // don't add to seen_twice because of presence in seen_once

            // second appearance:
            // remove num from seen_once
            // add num to seen_twice
            /**
             *
             */
            // third appearance:
            // don't add to seen_once because of presence in seen_twice
            // remove num from seen_twice
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }

        return seenOnce;
    }

    /**
     * https://leetcode-cn.com/problems/single-number-iii/
     * @param nums
     * @return
     */
    public int[] singleNumber555(int[] nums) {
        int n1 = 0;
        int n2 = 0;
        int tmp = 0;//两个只出现一次的 数字 异或 结果
        for (int n : nums) {
            tmp = tmp ^ n;
        }
        tmp &= -tmp;//找到 等于1 的 位
        for (int n : nums) {
            if ((n & tmp) == 0) {
                n1 = n1 ^ n;
            }else {
                n2 = n2 ^ n;
            }
        }
        return new int[]{n1, n2};
    }

    /**
     * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
     * @param nums
     * @return
     */
    public static int[] singleNumber4(int[] nums){
        int[] ret = new int[2];
        int tmp = 0;//两个只出现一次的 数字 异或 结果
        for (int n : nums) {
            tmp = tmp ^ n;
        }
        int idx = 0;//找到 值为1 的 序号
        for (int i = 0; i < 32; i++) {
            if ((tmp >> i & 1) == 1) {
                idx = i;
                break;
            }
        }
        //将 数组nums 分成两个数组
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();
        for (int n : nums) {
            if ((n >> idx & 1) == 1) {
                arr1.add(n);
            } else {
                arr2.add(n);
            }
        }
        int s1 = 0;
        int s2 = 0;
        for (int a : arr1) {
            s1 = s1 ^ a;
        }
        for (int a : arr2) {
            s2 = s2 ^ a;
        }
        ret[0] = s1;
        ret[1] = s2;
        return ret;
    }

}
